/*
 *  data.h
 *  kangmodb
 *
 *  Created by 강모 김 on 11. 5. 4..
 *  Copyright 2011 강모소프트. All rights reserved.
 *
 */

#ifndef _KD_DATA_H_
#define _KD_DATA_H_ (1)

#include "kdInfra.h"
#include "types.h"
#include "util.h"

/** @brief The interface class to pass data length and pointer between objects.
 */
class stgData
{
private :
	stgValueLength length_;
	void * data_;
public :
	stgData() : data_(NULL), length_(0)
	{
	};

	stgData(const void * data, const stgValueLength length) : data_((void*)data), length_((stgValueLength)length)
	{
		KD_ASSERT(data != NULL);
	};
	
	KD_INLINE const void * getData() const
	{
		return data_;
	};

	KD_INLINE const stgValueLength getLength() const
	{
		return length_;
	};

	int compare(const stgData & anotherData) const
	{
		return util::string_compare((const char*) data_, length_, (const char*)anotherData.getData(), anotherData.getLength() );
	};
};

/** @brief The versioned data dangled to a key in stgTable.
 */
typedef struct stgDataVersion
{
    /** @brief The pointer to the nextOldVersion. Transactions follow this link to find an apporopriate version to read considering its viewVersion.
	 */
    struct stgDataVersion * nextOldVersion;
	/** @brief This bit indicates if the KEY that dangles this DATA is deleted.
	 * When a transaction deletes a KEY in a table, this bit is set. 
	 * After the transaction is comitted, another garbage collecting logic deletes the KEY in the table assuring that no transaction can read the KEY.
	 */
	u64 deleted:1;
	/** @brief This field holds either a savepointID or commitVersion allocated by a committing transaction.
	 *  In the uncomittedLatestVersion list in stgTableKey, this field holds the savepoint ID.
	 *  New versions are created for different savepoints to make it easy to rollback to a savepoint ID.
	 *  When a transaction is committing, this field can have commit version even though it is in the uncommittedLatestVersion list.
	 *
	 *  In the latestVersion list in stgTableKey, this field holds the commit version.
	 *
	 *  c.f.> Is 47 bits enough to avoid overflowing commit verion in a busy system?
	 *        47 bits can represent an integer up to 140737488355328-1.
	 *        In a very busy system that 1 million transactions commit per second, the commit version will overflow in four years. 
	 */
	u64 spID_or_CommitVersion:47;
	/** @brief The length of data stored in the data field. 
	 */ 
	u64 dataLength:16;
	/** @brief The actual data immediatedly follows this structure. 
	 * So you need to allocate sizeof(stgTableData)+dataLength to store stgTableData and the data in a continuous memory.
	 * Also we need to align the starting address of data with 8 byte boundary so that we can type cast the data to a pointer of a structure.
	 */
	char data[1];
} stgDataVersion;

/** @brief initialize a data version. Called after the memory is allocated for a version.
 */
inline void initDataVersion( stgDataVersion * dataVersion )
{
	KD_ASSERT( dataVersion != NULL );
	dataVersion->nextOldVersion = NULL;
	dataVersion->deleted = 0;
	dataVersion->spID_or_CommitVersion = 0;
	dataVersion->dataLength = 0;
}

/** @brief The memory size to allocate for a stgDataVersion that will keep a data whose length is DataLen 
 */ 
// TODO : Optimize the size by not including char[1] in the stgDataDesc struct.
#define STG_DATA_VERSION_SIZE(DataLen) \
    (sizeof(stgDataVersion) + DataLen)

/** @brief The data descriptor associated with a key. It maintains data versions.
 *
 * The (key,value) pair stored in the skip list :
 *
 * (key=stgKey, value=stgDataDesc)
 *                      |
 *                      +-(latestVersion)-> stgDataVersion -> stgDataVersion -> ...
 *                      +-(uncommittedVersion)-> stgDataVersion -> stgDataVersion -> ...
 *                      +-(modifyingTransaction)-> stgTransaction   
 */
typedef class stgDataDesc
{
private :
	/** @brief The list of comitted versions. 
	 *  This points to the latest comitted version, and each version points to an older version. 
	 */
    struct stgDataVersion * comittedVersion_;
	
	// TODO : Consider adding paddings between comittedVersion_ and uncomittedVersion_ so that they reside in different cache line. 
	// Otherwise : whenever a writing tranasction modifies uncomittedVersion_, it will invalidate the same cacheline that the reading transactions get comittedVersion_.
	
	/** @brief The list of uncomitted versions.
	 *  This points to the latest uncomitted version, and each version points to an older version. 
	 *  Only one transaction have access to this field. 
	 *  Other transactions trying to modify the same key should Rollback to avoid version conflicts between modifying transactions.
	 */
    struct stgDataVersion * uncomittedVersion_;
	/** @breif The transaction that created new versions on uncomittedLatestVersion.
	 *  No need to have transaction ID, but a pointer to stgTransaction object is enough to compare if a transaction is the transaction modifying this key.
	 *  Upon restart recovery with shared memory regions, this field is set to NULL, and all versions linked in uncomittedLatestVersion are removed.
	 *  We don't use stgTransaction type here, but use (void *) because it is enough to compare the address between transactions.
	 */
	void * modifyingTransaction_;
	
public :

	stgDataDesc() 
	{
		comittedVersion_ = NULL;
		uncomittedVersion_ = NULL;
		modifyingTransaction_ = NULL;
	}
	~stgDataDesc()
	{
	}
	
	/** @brief Get the latest version 
	 */
	KD_INLINE stgDataVersion * getComittedVersion()
	{
		return comittedVersion_;
	}

	/** @brief Remove data versions whose versions are less than the given one.
	 *  This is called by the garbage collector. The given version should be the minimum version of view versions of all reading transactions.
	 */
	KD_VOID removeComittedVersionsLessThan(stgVersion version)
	{
		KD_TRY
		{
			// TODO : Implement
			KD_ASSERT( 0 );
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}
	
	/** @brief Add a new latest version to the comitted list. The original latest version becomes an old version. 
	 */
	KD_INLINE void addComittedVersion( stgDataVersion * newLatestVersion )
	{
		if (comittedVersion_ == NULL)
		{
			comittedVersion_ = newLatestVersion;
		}
		else 
		{
			newLatestVersion->nextOldVersion = comittedVersion_;
			comittedVersion_ = newLatestVersion;
		}
	}

	// TODO : change the name to addLatestUncomittedVersion
	/** @brief Get the latest version 
	 */
	KD_INLINE stgDataVersion * getUncomittedVersion()
	{
		return uncomittedVersion_;
	}

	/** @brief Remove and return the uncomitted latest version.
	 *  For updating the data with greater size, we need to remove the latest uncomitted version, 
	 *  and then add a new uncomitted version that is capable to hold the greater data size. 
	 */
	KD_INLINE stgDataVersion * removeUncomittedVersion()
	{
		stgDataVersion * theLatest = comittedVersion_;
		
		if (uncomittedVersion_ != NULL )
			uncomittedVersion_ = uncomittedVersion_->nextOldVersion;
			
		return theLatest;
	}
	
	/** @brief Add a new uncomitted latest version. The original uncomitted latest version becomes an old version. 
	 */
	KD_INLINE void addUncomittedVersion( stgDataVersion * newUncomittedVersion )
	{
		if (uncomittedVersion_ == NULL)
		{
			uncomittedVersion_ = newUncomittedVersion;
		}
		else 
		{
			newUncomittedVersion->nextOldVersion = uncomittedVersion_;
			uncomittedVersion_ = newUncomittedVersion;
		}
	}
	 
	/** @brief See if the transaction is the one modifying this data descriptor.
	 */
	KD_INLINE bool isModifyingTransaction( void * tx ) const
	{
		return modifyingTransaction_ == tx;
	}

	/** @brief Try modification on this data descriptor. Set *success to true if succeeded.
	 */
	KD_VOID tryModification( void * tx, bool * success )
	{
		KD_TRY
		{
			// TODO : Implement. Use CAS instead of mutex for the concurrency control.
			KD_ASSERT(0);
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}

	/** @brief Try modification on this data descriptor. Set *success to true if succeeded.
	 */
	KD_VOID endModification( void * tx )
	{
		KD_TRY
		{
			// TODO : Implement. Use CAS instead of mutex for the concurrency control.
			KD_ASSERT(0);
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}
	
	/** @brief Find the latest version, which is not higher than viewVersion. To see uncomitted changes, specify viewVersion with MAX_DATA_VERSION.
	 *  @param viewVersion The maximum verstion to read. Skip stgDataVersions with higher than viewVersion.
	 *                     Set it to MAX_DATA_VERSION to see uncomitted changes.
	 *  @param dataVersion If an appropriate version is found, set *dataVersion with the found one. Otherwise set it with NULL. 
	 */
	KD_VOID findLatestVersion(const stgVersion viewVersion, stgDataVersion ** dataVersion ) const
	{
		KD_ASSERT( viewVersion <= MAX_DATA_VERSION );
		KD_TRY
		{
			// TODO : Implement
			KD_ASSERT(0);
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}

	/** @brief Mark the latest uncomitted version "deleted" by setting the deleted bit in stgDataVersion with the given flag.
	 * @param spID Assert that the savepointID of latest uncomitted version matches spID.
	 * @isDeleted true if the version is deleted, false otherwise.
	 */
	KD_VOID setUncomittedVersionDeleted(const stgSavepointId spID, bool isDeleted)
	{
		KD_TRY
		{
			// TODO : Implement
			KD_ASSERT(0);
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}

	
	/** @brief In-place update the given data in the latest uncomitted version. 
	 *  Assert that the savepoint ID in the latest uncomitted version matches the given spID.
	 *  Assert that the latest uncomitted version has enough space to hold the new data.
	 */
	KD_VOID updateUncomittedVersion(const stgSavepointId spID, const stgData & data)
	{
		KD_TRY
		{
			// TODO : Implement
			KD_ASSERT(0);
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}
	
	/** @brief Add a new uncomitted version with spID. This function does not copy any data.  
	 *  @dataLength Prepare a sufficient space to hold a data with dataLength size.
	 */
	KD_VOID addUncomittedVersion(const stgSavepointId spID, const stgValueLength dataLength )
	{
		KD_TRY
		{
			// TODO : Implement
			KD_ASSERT(0);
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}
	/** @brief Remove uncomitted versions whose savepoint ID is greater than or equal to the given spID. 
	 * @param spID If the savepoint ID of a version is greater than or equal to spID, it will be removed.
	 * When Total Rollback happens, this function is called with spID=0. It will remove all uncomitted data versions in this desciptor.     
     * When Partial Rollback(Rollback to savepoint N) happens, this function is called with spID=N. It removes all uncomitted data versions where savepointID >= spID parameter.
	 * In this case, the latest version among remaining ones is dangled to uncomittedLatestVersion pointer.
	 */
	KD_VOID removeUncomittedVersions( const stgSavepointId spID )
	{
		KD_TRY
		{
			// TODO : Implement
			KD_ASSERT(0);
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}

	/** @brief Commit changes. 
	 * 1) Move the latest uncomitted version to the latest comitted version. Origial latest version becomes an old version. 
	 * 2) All stale uncomitted versions except the latest one are removed.
	 * 3) modifyingTransaction_ is set to NULL 
	 */
	KD_VOID commitChanges( const stgVersion commitVersion )
	{
		KD_TRY
		{
			// TODO : Implement
			KD_ASSERT(0);
		}
		KD_CATCH
		KD_FINALLY
		KD_END
	}
};

#endif /* _KD_DATA_H_ */
